一、學習目標

• 理解二分搜尋法的核心概念與適用場景
• 熟悉 C++ STL 中 lower_bound、upper_bound 的使用
• 透過 CSES 與 LeetCode 實戰鞏固二分搜尋的技巧
• 學會如何結合二分搜尋解決實際問題

二、二分搜尋法

核心概念

二分搜尋法 (Binary Search) 是一種在有序序列中高效搜尋的演算法。
透過不斷將搜尋範圍減半，時間複雜度只有 O(log n)。
適用條件:

• 陣列必須有序（遞增或遞減）
• 搜尋範圍可被縮小

C++ STL 提供的工具

C++ 提供內建二分搜尋工具：

範例:

vector<int> nums = {1, 2, 4, 4, 5, 7};
int target = 4;

auto lb = lower_bound(nums.begin(), nums.end(), target);
auto ub = upper_bound(nums.begin(), nums.end(), target);

cout << lb - nums.begin(); // 2
cout << ub - nums.begin(); // 4

三、CSES實戰演練

題目1:Ferris Wheel

原題:
https://cses.fi/problemset/task/1090

題意:
n 個小孩，每個小孩體重 w[i]
每個摩天輪車廂最多坐 2 個人，且總重量 ≤ x
求最少需要幾個車廂

解題思路:
將 w 排序
left 指向最輕的人
right 指向最重的人
如果 w[left] + w[right] <= x :一起做
否則最重的人單獨坐
每次使用一個車廂 → ans++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,maxWeight;
    cin>>n>>maxWeight;
    vector<int> weight(n);
    for(int i=0;i<n;i++){
        cin>>weight[i];
    }
    sort(weight.begin(),weight.end());
    int ferris=0;
    int i=0,j=n-1;
    while(i<=j){
        if(weight[i]+weight[j]<=maxWeight){
            ++i,--j; //輕重可以一起坐
        }
        else --j; //重的自己一台
        ferris++;
    }
    cout<<ferris<<endl;
    return 0;
}

時間複雜度分析：O(n log n)

題目2:Concert Tickets

原題:
https://cses.fi/problemset/task/1091
題意:
有 n 張演唱會門票，每張價格 h[i]
有 m 個顧客，每位顧客最多只願意付 t[i]
每位顧客希望買到「價格 ≤ t[i] 且最接近 t[i]」的票
如果沒有符合的票，輸出 -1

解題思路:
將票價 h 排序

• 使用 multiset 儲存票價
• 對於每個顧客 t[i]：
  • 找出 第一張 > t[i] 的票 → upper_bound
  • 再往回移一位，取得最接近 t[i] 且 ≤ t[i] 的票
  • 若找不到 → 輸出 -1
  • 找到後從 multiset 中刪掉

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    multiset<int> tickets;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        tickets.insert(x);
    }

    for (int i = 0; i < m; i++) {
        int t; cin >> t;
        auto it = tickets.upper_bound(t);
        if (it == tickets.begin()) {
            cout << -1 << endl;
        } else {
            --it;
            cout << *it << endl;
            tickets.erase(it);
        }
    }
}

四、Leetcode實戰演練

題目1: Binary Search

原題:
https://leetcode.com/problems/binary-search/description/

題意:
給一個升序整數陣列 nums 和 target
找出 target 的索引
若不存在，回傳 -1

解題思路:
二分搜尋
每次計算中點 mid
比較 nums[mid] 與 target
更新搜尋範圍直到找到或區間為空

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]<target) left=mid+1;
            else right=mid-1;
        }
        return -1;
    }
};

題目2:Find First and Last Position of Element in Sorted Array

原題:
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/

題意:
在升序陣列 nums 中，找出目標值 target 的起始索引與結束索引
如果不存在，回傳 [-1, -1]

解題思路:
使用 lower_bound 找到第一個 ≥ target 的位置
使用 upper_bound 找到第一個 > target 的位置
如果 lower_bound 超出邊界或值不等於 target → 回傳 [-1, -1]
否則答案是 [lb, ub-1]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto lb = lower_bound(nums.begin(), nums.end(), target);
        auto ub = upper_bound(nums.begin(), nums.end(), target);

        if (lb == nums.end() || *lb != target) return {-1, -1};
        return {int(lb - nums.begin()), int(ub - nums.begin() - 1)};
    }
};